package JavaCode.contest.weekly.n0_200.n171;

import java.util.HashMap;
import java.util.Map;

/**
 * author:fangjie
 * time:2020/1/12
 */
public class N4 {
    private final static  Map<Character,int[]> map;
    static {
        map=new HashMap<>(26);
        for (int i=0;i<26;i++)
        {
            map.put((char)(i+'A'),new int[]{i/6,i%6});
        }
    }
    public int minimumDistance(String word) {
        char[] strs=word.toCharArray();
        Map<String,Integer> dp=new HashMap<>();
        return slove(0,strs,'#','#',dp);
    }

    private int slove(int idx, char[] strs, char pre1, char pre2, Map<String, Integer> dp) {
        if (idx==strs.length)return 0;
        String key=pre1+pre2+","+idx;
        if(dp.containsKey(key))return dp.get(key);
        int res=Math.min(getDis(pre1,strs[idx])+slove(idx+1,strs,strs[idx],pre2,dp),
                getDis(pre2,strs[idx])+slove(idx+1,strs,pre1,strs[idx],dp));
        dp.put(key,res);
        return res;
    }

    private int getDis(char a,char b)
    {
        if(a=='#'||b=='#')return 0;
        int[] x1=map.get(a);
        int[] x2=map.get(b);
        return Math.abs(x1[0]-x2[0])+Math.abs(x1[1]-x2[1]);
    }
}
/*
二指输入法定制键盘在 XY 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处，例如字母 A 位于坐标 (0,0)，字母 B 位于坐标 (0,1)，字母 P 位于坐标 (2,3) 且字母 Z 位于坐标 (4,1)。

给你一个待输入字符串 word，请你计算并返回在仅使用两根手指的情况下，键入该字符串需要的最小移动总距离。坐标 (x1,y1) 和 (x2,y2) 之间的距离是 |x1 - x2| + |y1 - y2|。

注意，两根手指的起始位置是零代价的，不计入移动总距离。你的两根手指的起始位置也不必从首字母或者前两个字母开始。



示例 1：

输入：word = "CAKE"
输出：3
解释：
使用两根手指输入 "CAKE" 的最佳方案之一是：
手指 1 在字母 'C' 上 -> 移动距离 = 0
手指 1 在字母 'A' 上 -> 移动距离 = 从字母 'C' 到字母 'A' 的距离 = 2
手指 2 在字母 'K' 上 -> 移动距离 = 0
手指 2 在字母 'E' 上 -> 移动距离 = 从字母 'K' 到字母 'E' 的距离  = 1
总距离 = 3
示例 2：

输入：word = "HAPPY"
输出：6
解释：
使用两根手指输入 "HAPPY" 的最佳方案之一是：
手指 1 在字母 'H' 上 -> 移动距离 = 0
手指 1 在字母 'A' 上 -> 移动距离 = 从字母 'H' 到字母 'A' 的距离 = 2
手指 2 在字母 'P' 上 -> 移动距离 = 0
手指 2 在字母 'P' 上 -> 移动距离 = 从字母 'P' 到字母 'P' 的距离 = 0
手指 1 在字母 'Y' 上 -> 移动距离 = 从字母 'A' 到字母 'Y' 的距离 = 4
总距离 = 6
示例 3：

输入：word = "NEW"
输出：3
示例 4：

输入：word = "YEAR"
输出：7

 */
